Distributed computer systems typically comprise multiple computers connected to each other by a communications network. In some distributed computer systems, the networked computers can concurrently access shared data. Such systems are sometimes known as parallel computers. If a large number of computers are networked, the distributed system is considered to be "massively" parallel. As an advantage, massively parallel computers can solve complex computational problems in a reasonable amount of time.
In such systems, the memories of the computers are collectively known as a distributed shared memory. It is a problem to ensure that the data stored in the distributed shared memory are accessed in a coherent manner. Coherency, in part, means that only one computer can modify any part of the data at any one time, otherwise the state of the data would be nondeterministic.
Some distributed computer systems maintain data coherency using specialized control hardware. The control hardware may require modifications to the components of the system such as the processors, their caches, memories, buses, and the network. In many cases, the individual computers may need to be identical or similar in design, e.g., homogeneous.
As a result, hardware controlled shared memories are generally costly to implement. In addition, such systems may be difficult to scale. Scaling means that the same design can be used to conveniently build smaller or larger systems.
More recently, shared memory distributed systems have been configured using conventional workstations or PCs connected by a conventional network as a heterogeneous distributed system.
In such systems, data access and coherency control are typically provided by software-implemented message passing protocols. The protocols define how fixed size data blocks and coherency control information is communicated over the network. Procedures which activate the protocols can be called by "miss check code." The miss check code is added to the programs by an automated process.
States of the shared data can be maintained in state tables stored in memories of each processor or workstation. Prior to executing an access instruction, e.g., a load or a store instruction, the state table is examined by the miss check code to determine if the access is valid. If the access is valid, then the access instruction can execute, otherwise the protocols define the actions to be taken before the access instruction is executed. The actions can be performed by protocol functions called by the miss handling code.
The calls to the miss handling code can be inserted into the programs before every access instruction by an automated process known as instrumentation. Instrumentation can be performed on executable images of the programs.
FIG. 1 shows an example miss check code 100 for a program which is to execute on a RISC type of computer. In this implementation, all of the memories of the distributed computers are partitioned so that the addresses of the shared memory are always higher than the addresses of the non-shared memory. In addition, the implementation maintains coherency state information for fixed size quantities of data, for example "lines." Obviously, the fixed size of the lines used by any particular application can be set to be smaller or larger than 64 bytes. Partitioning the addresses of shared memory, and using fixed lines simplifies the miss check code, thereby reducing overhead.
First, in step 101, save the content of any registers that are going to be used by the miss check code 100 on a stack. In step 102, determine the target address of the access instruction, using the offset and base as specified in the operands of the instruction. The access instruction in this example is a store. A store access is valid if the processor modifying the data stored at the target address has exclusive ownership of the data.
In steps 103-104, determine if the target address is in non-shared memory. If this is true, then skip the rest of miss check code 100, restore the registers at 131 and execute the memory access instruction, step 132. In this case, the overhead is about seven instructions.
Otherwise, if the target address is in shared memory, then in step 105, determine the index of the line including the target address. If the size of the line is an integer power of two, for example 64 bytes, the line index can be computed using a simple shift instruction.
As shown in step 106, the line index can be used to reference the corresponding entry of the state table. In the exemplary implementation, each entry in the state table is a byte. Obviously, if the number of different states is small, for example, the states can be indicated with two bits, then the size of the state table can be reduced. However, by making the entries smaller, it becomes more difficult to extract state information, since most computers do not conveniently deal with addressing schemes and data operations which are less than eight bits.
In step 107-108, the table entry is loaded, and in step 109, determine if the state of the line containing the target address is, for example, EXCLUSIVE. If true, then skip the step 120, and restore the registers from the stack in step 131. In this case, the overhead is about thirteen instructions. Otherwise, call the miss handling code to gain exclusive control over the data in step 120.
Most prior art distributed shared memory systems manage data coherency at fixed size data quantities. In systems using coarse-grained quantities, the unit of data transfer between the processors over the network is typically a virtual memory page, for example, a page of 2K, 4K, 8K bytes, or the like. In systems using fine-grained quantities, the unit of data transfer is typically a line, for example 32 or 64 bytes.
It is desired to allow the unit of data transfer between processors of a distributed memory system to be matched to the size of the underlying data structures. Coherency control for large data structures should allow for the transfer of large units of data so that the time to transfer the data can be amortized. Coherency for smaller data structures should allow the transfer of smaller units of data. It should also be possible to use small units of coherency for large data structures that are subject to false sharing. False sharing is a condition where independent data elements are stored in a single data structure.